The present invention relates to programmable logic devices (PLDs), and more particularly to a method for assigning costs to routing resources in PLDs.
A typical FPGA comprises a large plurality of configurable logic blocks (CLBs) surrounded by input-output blocks and interconnectable through a routing structure. The routing structure comprises many interconnect wires and associated programmable interconnect points (PIPs). In one embodiment, a PIP contains a pass transistor that can be turned on and off, thereby allowing an associated interconnect wire to be either connected or disconnected (depending on the state of the transistor) to other circuit elements. The CLBs and routing structure of the FPGA are arranged in an array or in a plurality of sub-arrays wherein respective CLBs and associated portions of the routing structure are placed edge to edge in what is commonly referred to as a tiled arrangement. An example of such a tiled arrangement is described in U.S. Pat. No. 5,914,616 entitled xe2x80x9cFPGA Repeatable Interconnect Structure with Hierarchical Interconnect Lines.xe2x80x9d The CLB portion of a tile comprises a plurality of primitive cells which may be interconnected in a variety of ways to perform a desired logic function. For example, a CLB may comprise a plurality of lookup tables (LUTs), multiplexers and registers. As used herein, the term xe2x80x9cprimitive cellxe2x80x9d means the lowest level of user accessible component.
When an FPGA comprises thousands of CLBs in large arrays of tiles, the task of establishing the required multitude of interconnections between primitive cells inside a CLB and between the CLBs becomes so onerous that it requires software tool implementation. Accordingly, the manufacturers of FPGAs, including Xilinx, Inc., the assignee hereof, have developed place and route software tools that may be used by their customers to implement their respective designs. Place and route tools not only provide the means of implementing users"" designs, but can also provide an accurate and final analysis of static timing and dynamic power consumption for an implemented design scheme.
Routing tools are very important in determining the performance of a circuit implemented on a FPGA. If signals are not routed properly, excessive amount of resources are used to carry signals. This could lead to design with poor timing and power performance. Further, routing tools are very difficult to develop and very time consuming to execute. Consequently, it is important to improve routing tools.
The present invention involves a method for routing a signal from a source to a destination in a PLD that has a plurality of routing resources. The topology information of each of the plurality of resources is obtained. In one embodiment, the PLD can be geometrically divided into an array of logical tiles. These tiles can be used to supply the topology information. Each of the plurality of resources is assigned a cost based on its associated topology information. For example, the cost can be set as the number of tiles the resource intersects (xe2x80x9cspanxe2x80x9d). A signal path between the source and destination can be routed using the cost information for the resources.
In one embodiment of the present invention, the cost is set as the maximum value between the vertical and vertical spans (instead of the total span). This embodiment often increases the speed of routing.
The above summary of the present invention is not intended to describe each disclosed embodiment of the present invention. The figures and detailed description that follow provide additional example embodiments and aspects of the present invention.